package algorithms.a08MinimumSpanTrees;

import algorithms.a04heap.IndexMinHeap;
import algorithms.a04heap.MinHeap;
import com.google.common.collect.Sets;

import java.net.URI;
import java.util.Iterator;
import java.util.Set;

/**
 * 使用Prim算法求图的最小生成树
 * 优化版 最小堆改为最小索引堆
 * @author 王昊然
 * @create 2018-03-06 15:15
 **/
public class PrimMST<Weight extends Number & Comparable> {

    private WeightedGraph<Weight> g;//图，前提是只有一个联通分量
    private IndexMinHeap<Edge<Weight>> mh; //最小生成树的边组成的最小堆
    private boolean[] marked; //所有点，最小生成树的点标记为true
    private Set<Edge<Weight>> edges; //最小生成树边的集合
    private Edge[] edgeTo; //存储过程中每个点使用的最小边
    private Number mstWeight;        // 最小生成树的权值（边权值的和）

    public PrimMST(WeightedGraph<Weight> graph) {
        this.g = graph;
        mh = new IndexMinHeap<Edge<Weight>>(g.V()); //只开辟顶点数量的空间即可
        marked = new boolean[g.V()];
        edges = Sets.newHashSet();
        mstWeight = new Double(0);
        edgeTo = new Edge[g.V()];

        startPrim(0);
    }

    /**
     * 从一个未标记的点开始（过程不太好理解，多看ppt的动画演示）
     * 1 遍历点的所有边，将属于横切边的,根据点的值，放入索引堆的对应位置
     * 2 1中各边去最小权值边，放到edgeTo中
     * 3 索引堆中取顶边：
     * 3-1如果边的两个点都没有被mark，说明当前边就是要找的一条边，放入最小树集合，计算权值和，visit另一个点
     * 3-2如果边的两个点都已经被mark，说明已经有其他路径将两点相连，该边废弃掉
     * 3-3不会存在两个点都未被标记的情况，这样的边是不会放到堆里的
     * 4 最小堆为空时停止
     *
     * @param v
     * @date: 2018/3/6 15:34
     * @author: 王昊然
     */
    private void startPrim(int v) {

        visit(v);

        while( !mh.isEmpty() ){
            // 使用最小索引堆找出已经访问的边中权值最小的边
            // 最小索引堆中存储的是点的索引, 通过点的索引找到相对应的边
            int minI = mh.extractMinIndex();
            assert( edgeTo[minI] != null );
            edges.add( edgeTo[minI] );
            visit( minI );
        }

        // 计算最小生成树的权值
        Iterator<Edge<Weight>> iterator = edges.iterator();
        while( iterator.hasNext() )
            mstWeight = mstWeight.doubleValue() + iterator.next().wt().doubleValue();
    }

    /**
     * 将点连接的边，在当前情况下属于横切边的，都放到堆中
     * 注意“当前情况”的理解含义
     * @param v
     * @date: 2018/3/6 16:56
     * @author: 王昊然
     */
    private void visit(int v) {

        marked[v] = true;
        Iterator<Edge> iterator = g.adj(v).iterator();
        while (iterator.hasNext()) {
            Edge edge = iterator.next();
            int w = edge.other(v);
            if (!marked[w]) {//横切边
                if(edgeTo[w]==null){
                    edgeTo[w] = edge;
                    mh.insert(w, edge);
                }else{
                    if(edgeTo[w].compareTo(edge)>0){//对同一个点，如果之前存的边大，用新边替掉
                        edgeTo[w] = edge;
                        mh.change(w, edge);
                    }
                }
            }
        }
    }

    // 返回最小生成树的所有边
    public Set<Edge<Weight>> mstEdges(){
        return edges;
    };

    // 返回最小生成树的权值
    public Number result(){
        return mstWeight;
    };

    public static void main(String[] args) throws Exception{

        URI fileUri = LazyPrimMST.class.getResource("testG1.txt").toURI();
        int V = 8;

        SparseWeightedGraph<Double> g = new SparseWeightedGraph<Double>(V, false);
        ReadWeightedGraph readGraph = new ReadWeightedGraph(g, fileUri);

        // Test Prim MST
        System.out.println("Test Prim MST:");
        PrimMST<Double> primMST = new PrimMST<Double>(g);
        Set<Edge<Double>> mst = primMST.mstEdges();
        Iterator<Edge<Double>> iterator = mst.iterator();
        while(iterator.hasNext())
            System.out.println(iterator.next());

        System.out.println("The MST weight is: " + primMST.result());
    }

}
